package 动态规划;

public class No1143最长公共子序列 {

    /**
     * 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
     * 一个字符串的 子序列 是指这样一个新的字符串：
     * 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
     * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
     * 两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
     * 若这两个字符串没有公共子序列，则返回 0。
     *
     * 示例 1:
     * 输入：text1 = "abcde", text2 = "ace"
     * 输出：3
     * 解释：最长公共子序列是 "ace"，它的长度为 3。
     * 示例 2:
     * 输入：text1 = "abc", text2 = "abc"
     * 输出：3
     * 解释：最长公共子序列是 "abc"，它的长度为 3。
     * 示例 3:
     * 输入：text1 = "abc", text2 = "def"
     * 输出：0
     * 解释：两个字符串没有公共子序列，返回 0。
     *  
     * 提示:
     * 1 <= text1.length <= 1000
     * 1 <= text2.length <= 1000
     * 输入的字符串只含有小写英文字符。
     */

    /**
     * dp理解:
     * x,y轴分别是两个字符串分别取前x个,前y个,然后多少个相同的
     */
    public int longestCommonSubsequence(String text1, String text2) {

        int[][] dp=new int[text1.length()][text2.length()];

        /**
         * 1.第一排和第一列的值[0,0...n][0...n,0]不都与[0,0]相等,也要用for一个个判断
         * 2.采用两边包,就无需注意j的边界
         */
        if(text1.charAt(0)==text2.charAt(0)){
            dp[0][0]=1;
        }
        for (int i = 1; i < text2.length(); i++) {
            if(text1.charAt(0)==text2.charAt(i)){
                dp[0][i]+=1;
            }else{
                dp[0][i]=dp[0][Math.max(i-1,0)];
            }
        }

        //双边,j从1开始,就不用判断if(j-1<0)了
        for (int i = 1; i < text1.length(); i++) {
            if(text2.charAt(0)==text1.charAt(i)){
                dp[i][0]+=1;//这里注意可能会加两次
            }else{
                dp[i][0]=dp[Math.max(i-1,0)][0];
            }
        }

        for (int i = 1; i < text1.length(); i++) {
            for (int j = 1; j < text2.length(); j++) {
                if(text1.charAt(i)==text2.charAt(j)){
                    //i==j j-1也要有边界
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    //不相等
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }

        return dp[text1.length()-1][text2.length()-1];
    }

    public static void main(String[] args) {
        No1143最长公共子序列 n=new No1143最长公共子序列();
        int result = n.longestCommonSubsequence("dknkdizqxkdczafixidorgfcnkrirmhmzqbcfuvojsxwraxe",
                "dulixqfgvipenkfubgtyxujixspoxmhgvahqdmzmlyhajerqz");
        System.out.println(result);
    }

}
